As the semiconductor industry continues to rapidly improve silicon chip performance, new digital processing applications have been developed to take advantage of the increase in processing speed. For example, traditional radio signal transmission methods that utilize analog signal processing techniques to transmit analog radio signals in analog format have gradually been replaced by newer signal transmission methods that utilize digital signal processing techniques to convert the analog radio signals to binary code (signal digitization) prior to transmission. Surprisingly, even with the analog to binary conversion step (and its potential for introducing translational errors), radio signal transmission methods using digital signal processing techniques still have better results (e.g., higher fidelity, resistance to interference, etc.) than those methods that still utilize analog signal processing techniques. As a result, many new potential applications for digital signal processing have been proposed.
Digital broadcasting systems (e.g., Digital Audio Broadcasting (DAB) and Digital Video Broadcasting (DVB)), have already started replacing conventional analog broadcasting systems used by many broadcasters today. A DAB system transmits a plurality of digital stereo sound signals (that are in bit-synchronism with each other) in a Coded Orthogonal Frequency Division and Multiplexing (COFDM) signal packet using a plurality of individual synchronized transmitters. Under COFDM, the digital data stream of each stereo signal is divided, prior to transmission, into multiple sub-signals each of which is separately transmitted by a signal carrier. After the sub-signals are received by a receiver, they are re-combined to convey the information held in the original digital stereo signal. DAB systems developed for audio broadcasting exhibit good signal transmission characteristics as they minimize distortions of the radio signals due to transmission distance and external interference.
In U.S. Pat. No. 5,521,943 to Dambacher titled “COFDM combined encoder modulation for digital broadcasting sound and video with PSK, PSK/AM, and QAM techniques,” a modulation method is disclosed that achieves dual capacity for each COFDM signal packet. A circuit configuration having dual IFFT (Inverse Fast Fourier Transform), D/A-conversion and I/Q-modulation (QAM) is implemented to transmit 8 phase shift keying (PSK) and 2 amplitude modulation (AM) signals. The disclosure of this reference is incorporated herein by reference as if set forth in full.
Referring to the DVB-T (DVB-Terrestrial) specification titled “ETSI EN 300 744 V1.5.1 (2004-06),” an Orthogonal Frequency Division and Multiplexing (OFDM) frame structure is introduced. The transmitted signal is organized into frames which consists of 68 OFDM symbols and has a duration time of Tf. Each symbol consists of a set of K=6,817 carriers or K=1,705 carriers and is transmitted with a duration Ts. The duration Ts is further comprised of a use interval with duration Tu and a guard interval with a duration Δ. The carriers are indexed by k ε[K min;K max]. The disclosure of this reference is incorporated herein by reference as if set forth in full.
The emitted signal defined in the DVB-T specification is described by the following expression:
            s      ⁡              (        t        )              =          Re      ⁢              {                              ⅇ                          j2π              ⁢                                                          ⁢              fct                                ⁢                                    ∑                              m                =                0                            ∞                        ⁢                                          ∑                                  l                  =                  0                                67                            ⁢                                                ∑                                      K                    ⁢                                                                                  ⁢                    min                                                        K                    ⁢                                                                                  ⁢                    max                                                  ⁢                                                      c                                          m                      ,                      l                      ,                      k                                                        ×                                                            ψ                                              m                        ,                        l                        ,                        k                                                              ⁡                                          (                      t                      )                                                                                                          }              where                    ψ                  m          ,          l          ,          k                    ⁡              (        t        )              =          ⅇ              j2π        ⁢                                  ⁢                                            k              ′                        ⁡                          (                              t                -                Δ                -                                  l                  ×                  Ts                                -                                  68                  ×                  m                  ×                  Ts                                            )                                /          Tu                                                  while          ⁢                                          (                      l            +                          68              ×              m                                )                ×        Ts            ≦      t      ≦                        (                      l            +                          68              ×              m                        +            1                    )                ×        Ts        ⁢                                  ⁢        or        ⁢                                  ⁢        else        ⁢                                  ⁢                              ψ                          m              ,              l              ,              k                                ⁡                      (            t            )                                =    0.  where:    k denotes the carrier number;    l denotes the OFDM symbol number;    m denotes the transmission frame number;    K is the number of transmitted carriers;    Ts is the symbol duration;    Tu is the inverse of the carrier spacing;    Δ is the duration of the guard interval;    fc is the central frequency of the radio frequency (RF) signal;    k′ is the carrier index relative to the center frequency, k′=k−(Kmax+Kmin)/2;    cm,0,k complex symbol for carrier k of the Data symbol no. 1 in frame number m;    cm,1,k complex symbol for carrier k of the Data symbol no. 2 in frame number m;    cm,67,k complex symbol for carrier k of the Data symbol no. 68 in frame number m; and    the cm,l,k values are normalized modulation values.
The equation presented above can be further simplified for the emitted signal during the period between t=0 to t=Ts as described by the following expression:
            s      ⁡              (        t        )              =          Re      ⁢              {                              ⅇ                          j2π              ⁢                                                          ⁢              fct                                ⁢                                    ∑                              K                ⁢                                                                  ⁢                min                                            K                ⁢                                                                  ⁢                max                                      ⁢                                          c                                  0                  ,                  0                  ,                  k                                            ×                              ⅇ                                  j2π                  ⁢                                                                          ⁢                                                                                    k                        ′                                            ⁡                                              (                                                  t                          -                          Δ                                                )                                                              /                    Tu                                                                                      }                        with      ⁢                          ⁢              k        ′              =          k      -                        (                                    K              ⁢                                                          ⁢              max                        +                          K              ⁢                                                          ⁢              min                                )                /        2.            
This simplified equation resembles the following inverse Discrete Fourier Transform (DFT) expression:
      X    n    =            1      N        ⁢                  ∑                  q          =          0                          N          -          1                    ⁢                        X          q                ⁢                              ⅇ                          j2π              ⁢                                                          ⁢                              nq                /                N                                              .                    
Various efficient Fast Fourier Transform (FFT) algorithms exist to perform DFT and its inverse IDFT. An implementation of a DVB-T modulator can also be used the perform an IFFT to generate N samples Xn. A DVB signal is coded and interweaved in the early stage, then, mapped and inserted with parameter signals that are modulated by the OFDM specification as defined by the standard. Finally, the digitally processed information is transmitted via the RF front end block and broadcast through the air.
FFT algorithms are not only employed in digital broadcasting systems, but also in digital signal processors, which use FFT algorithms to transfer discrete time signals from a time domain to a frequency domain. A method termed reverse transformation also exists to reverse the FFT transfer process by, transferring discrete time signals from a frequency domain to a time domain.
As used herein, complex numbers are numbers with the form a+ib where a and b are real numbers and i represents the square root of negative number. Any complex number to a complex power also results in a complex number. Each complex number has its own position on the complex plane, which has a real axis and an imaginary axis. A complex number can be represented by polar coordinates with a modulus and an argument where the modulus is the distance to the origin of the complex plane and the argument is the angular coordinate. Modulus and argument are sometimes also called amplitude and phase, especially with regards to Fourier Transforms used in electronic components and devices. Thus, a complex number a+ib can also be represented by the exponential form reiφ where e is the number 2.71828, r is the modulus and Ψ is the argument from its representation in polar coordinates. Moreover, a complex number a+ib can be written as r*(cos(Ψ)+i*sin(Ψ)) which means that eix=cos(x)+i·sin(x).
In electronic communication systems, both the “real” and “imaginary” (i.e., phase of the signal) parts of a signal are processed. Fourier Transforms are easily applied against communication signals that are exponential forms of complex numbers. For example, the continuous Fourier Transform function G(t) in time domain is defined as:
      G    ⁡          (      f      )        =            ∫              -        ∞            ∞        ⁢                  g        ⁡                  (          t          )                    ⁢              ⅇ                              -            2                    ⁢          π          ⁢                                          ⁢          ⅈ          ⁢                                          ⁢                      f            ⁢            t                              ⁢              ⅆ        t            and the inverse transform is defined as:
      g    ⁡          (      t      )        =            ∫              -        ∞            ∞        ⁢                  G        ⁡                  (          f          )                    ⁢              ⅇ                              -            2                    ⁢          π          ⁢                                          ⁢          ⅈ          ⁢                                          ⁢                      f            ⁢            t                              ⁢                        ⅆ          f                .            
This expression uses complex numbers in exponential form, which can be further split into cos and sin triangular functions to facilitate the actual calculation. This is a one-dimensional Fourier Transform operation that transforms a signal from time domain to frequency domain. When a signal is in the frequency domain, the amplitude of the function determines how much of it is in the signal and the phase determines the frequency components.
In U.S. Pat. No. 6,411,978 to Naveh et al. titled “Mechanism for block floating point FFT hardware support on a fixed point digital signal processor,” a hardware mechanism is introduced to deal with the overflow problem in a digital signal processor while a block floating point Fast Transform is employed to improve signal to quantization noise ratio performance. In this disclosure, a general radix-2 Decimation In Time (DIT) FFT method is presented showing an output vector (c, d) in terms of an input vector (a, b) as follows:
c=a+WNk·b and d=a−WNk·b where all the numbers are general complex numbers.
Each output is the sum of two numbers, for example, c is the sum of a and WNk·b, where the term WNk is a “twiddle factor” defined as WNk=e−2πjnk/N, j is an imaginary number and the magnitude of WNk is unity. In the calculation, the product WNk·b can change the magnitude of the real and/or imaginary part of the complex number by a factor of √{square root over (2)}. That is, in the computation of DIT FFT, the component under manipulation can grow up to √{square root over (2)} times the real and/or imaginary parts of the complex number b.
One problem that exists with the FFT computation involves the variation in the dynamic range of complex numbers. As used herein, the dynamic range is a range between the maximum possible value and the minimum possible value. In certain scenarios, the dynamic range can grow by a factor of up to 2. For example, in the mentioned output vector (c, d), the dynamic range of the absolute value of c and d are listed as follows:abs(c)≦2·max(abs(a),abs(b))andabs(d)≦2·max(abs(a),abs(b)).
When the dynamic range in a fixed point digital signal processor (DSP) grows, solutions are needed to overcome the overflow problem. The simplest solution is to divide each input vector by N, where N is the number of inputs. However, this solution results in low signal to quantization noise ratio (SQNR). A second solution is to divide each result of each operation by 2, however, this fails to obtain a high enough SQNR for most communications applications. A third solution is to use a block floating point technique such as block floating point (BFP) FFT. BFP FFT redoes the calculation whenever any overflows are detected. This approach improves the overall SQNR but sacrifices efficiency and introduces a measure of uncertainty with respect to the number of necessary cycles to accomplish a computation.
In U.S. Pat. No. 6,411,978, a loadable register that stores a threshold value for detecting the overflows is disclosed. The actual overflow detection can be controlled by a software program. Although it may be ideal to utilize programmable software to detect overflows, the time delays caused by the slow processing steps of the software hampers digital signal processing performance. Each of the above referenced patents are incorporated herein by reference as if set forth in full.